package com.test.daily.leetcode.y2022.m07.day0704.v01;

/**
 * @author Tom on 2022/7/4
 */
public class Solution {
    public static int ways1(int[] arr){
        if(arr == null){
            return -1;
        }
        if(arr.length <= 2){
            return arr.length;
        }
        return process1(arr, 0, arr.length - 1);
    }
    public static int process1(int[] arr, int left, int right){
        if(left == right){
            return 1;
        }
        int ans = right - left + 1;
        for(int i = left + 1; i <= right; i++){
            ans = Math.min(ans, process1(arr, left, i - 1) + process1(arr,i, right) - (arr[i+1] == arr[left]? 1 : 0));
        }
        return ans;
    }
    public static int ways2(int[] arr){
        if(arr == null){
            return -1;
        }
        if(arr.length == 1){
            return 1;
        }
        int N = arr.length - 1;
        int[][] dp = new int[N][N];
        return process2(arr, 0, arr.length - 1, dp);
    }
    public static int process2(int[] arr, int left, int right, int[][] dp){
        if(dp[left][right] != 0){
            return dp[left][right];
        }
        int ans = right - left + 1;
        if(left == right){
            ans = 1;
        }else {
            for(int i = left + 1; i <= right; i++){
                ans = Math.min(ans, process2(arr, left, i - 1, dp) + process2(arr,i, right, dp) - (arr[i+1] == arr[left]? 1 : 0));
            }
        }
        dp[left][right] = ans;
        return dp[left][right];
    }

    public static int ways3(int[] arr){
        if(arr == null){
            return -1;
        }
        if(arr.length == 1){
            return 1;
        }
        int N = arr.length - 1;
        int[][] dp = new int[N][N];
        for (int i = 0; i < N - 1; i++) {
                dp[i][i] = 1;
                dp[i][i+1] = arr[i] == arr[i-1] ? 1: 2;
        }
        dp[N-1][N-1] = 1;
        for (int left = 1; left < N-1; left++) {
            for (int right = left+2; right < N; right++) {
                int ans = right - left + 1;
                for(int i = left + 1; i <= right; i++){
                    ans = Math.min(ans, dp[left][i - 1] + dp[i][right] - (arr[i+1] == arr[left]? 1 : 0));
                }
            }
        }
        return dp[0][arr.length - 1];
    }
}
